package com.lenl.arithmetic.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-04-30 22:31
 * @description 希尔排序
 * 优化后的插入排序
 *
 */
public class ShellSort {
    public static void main(String[] args) {
        //int[] arr={8,9,1,7,2,3,5,4,0,6};
        int[] arr=getArr(80);

        SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyyyMMdd_HHmmssSSS");
        System.out.println(simpleDateFormat.format(new Date()));

        //交换方式的希尔排序比普通插入排序更慢
        //InsertSort.doInsertSort(arr);
        //doShellSort(arr);
        //移位的希尔排序贼快
        moveShellSort(arr);

        System.out.println(simpleDateFormat.format(new Date()));
        //System.out.println(Arrays.toString(arr));
    }

    //交换式的希尔排序
    public  static void doShellSort(int[] arr){
        int len=arr.length;
        int group=len/2;

        while(group>0){
            for (int i=group;i<len;i++){
                for(int j=i-group;j>=0;j-=group){
                    //如果当前元素大于加上步长后的元素的值，交换
                    if(arr[j]>arr[j+group]){
                        arr[j]=arr[j]+arr[j+group];
                        arr[j+group]=arr[j]-arr[j+group];
                        arr[j]=arr[j]-arr[j+group];
                    }
                }
            }
            group/=2;
        }
    }
    //移位法的希尔排序
    public static void moveShellSort(int[] arr){
        //增量group，并逐步缩小增量
        for(int group=arr.length/2;group>0;group/=2){
            //从第group个元素，诸葛对其所在的组继续宁直接插入排序
            for(int i=group;i<arr.length;i++){
                int j=i;
                int temp=arr[j];
                if(arr[j]<arr[j-group]){
                    while (j-group>=0&&temp<arr[j-group]){
                        //移动
                        arr[j]=arr[j-group];
                        j-=group;
                    }
                    //退出while循环后，给temp找到插入的位置
                    arr[j]=temp;
                }
            }
        }

    }


    public static int[] getArr(int len){
        int[] arr=new int[len];
        //测试速度
        for (int i=0;i<arr.length;i++){
            arr[i]=(int)(Math.random()*8000000);//[0,8000000)
        }
        return arr;
    }

}
